3D Coding TAT - Plants, Trees And Forests
1: A common theme
After writing most of this big document I have noticed a common theme which is repeated many times throughout. And it is "hierarchical structures" or put another way:
From tiny data acorns,
mighty optimized trees grow.
As 3d programming requires a large amount of effort before even the most primitive engine is created with many small data handling procedures there doesn't seem to be (at first) any general approach to optimizing the render pipeline. But using trees structures with parents and siblings is an elegant solution for just about every aspect of a 3d engine, from clipping and object definition to dynamic detail levels the tree appears to be king. Even depth sorting and collision detection can benefit from a tree approach. It is not just in sorting data or string searching that tree structures are incredibly useful, giving vast gains with little effort, but depending on how a tree is defined it can reduce the considerable workload in a large number of areas. Normally an item's position within a tree is based upon some spacial attribute (e.g. distance) instead of some characteristic (e.g. colour, texture, size, vertices). As I have previously mentioned clipping can benefit from a tree or a 'forest' approach. The branching or sub-dividing data structure of a tree doesn't have to be only used to describe every polygon of every object, it can be extended into a much bigger hierarchical structure. For example imagine we did store every polygon in a single tree, now what happens when we want to delete an object and all it's polygons from it? A list of polygons for each object could be defined and this could be used to delete nodes from the tree. But what if we want to re-use the same object a number of times?
It is much better to use a 'forest' structure, i.e. trees within trees. Now instead of a single polygon at each node we can simply point to another sub-tree (an object). Of course we would also need to keep some of the information from the world-tree (the forest) and pass it onto the sub-tree. This way we could re-use objects again and again just by pointing to the same sub-tree. Now the forest contains the spacial map of all objects positions, and the sub-trees contain the polygon information themselves. This is a much more sensible way to go about it. To remove an object from the forest we simply kill the single link to the sub-tree and all it's polygons are never visited or rendered. To reverse this and plant a new object we can create a new node branch in the forest and point that to the object's sub-tree.
Clipping becomes much faster using this hierarchical method. If we can reject the node branch in the forest then we can also reject the sub-tree and every one of its polygons. And taking this idea further, if we can reject part of the forest then we can also reject all of it's sub-trees and all of their polygons. Collision detection can use the spacial coherence of each sub-tree in the forest because we only need to check it's surrounding neighbouring and not every other object. Even then we only really need to check for collision between objects which move. E.g. check the player against the surrounding objects and don't bother checking every static wall against every other static wall. (Of course moving doors and lifts could possibly need checking.)
We can also implement an efficient horizon cut-off point when rendering the world forest. If an object's position is beyond a certain distance from the view point then we can reject the entire sub-tree and its polygons. Even the sub-trees themselves could be built using a detail tree instead of just a polygon list. This would need to be created in a coarse-to-fine order with the smallest detail at the tips of the tree and the bigger coarse stuff near the root. Once we get to our horizon cut-off point we can stop following the tree down. So the more distant the object, the less of the tree we need to follow and the fewer the number of polygons that we need to render.
But this means we lose the ability to order the tree using some other selection method (e.g. depth sorting). As far as I know a tree can only be used for one purpose with one ordering method. A tree created for depth-sorting IS NOT the same as a tree built for a detail leveling. The only feasible solution I can think of at this time is to built two individual trees and cross reference the outcome of both, possibly using a simple flag system. For example one tree might describe various detail levels and another tree might describe directions for visibility tests. Only if a polygon passes BOTH tests will it be rendered, if it fails either one then it is simply rejected. As the trees can not be combined because their build orders conflict another solution could be to take the output from one tree (the items which were NOT rejected) and build a second tree from them. But this would incur the performance penalty of having to sort the unorder output from the first tree, navigating and building the second. In this case the flag system should work out much faster, even after having to clear the flags in the first place. When the last tree is being processed we only need to test each item's flag (assuming it passed the last test as well).
This flag system could be applied to any number of tree "sieves", each one would reduce the number of polygons yet further until we end up with every polygon, a few or none. The greater the number of tree sieve stages the fewer the number of polygons (in theory). But you must also remember that with each new sieve tree more navigation is required, often tracing paths which lead to already rejected items. Until some smart cookie comes up with a method to sort items correctly for multiple attributes then there is still room for new discovery.
After recently reading a chapter in a book called Knuth's Fundamental Algorithms about trees I was amazed at how long ago tree structure had been developed, the book itself was dated about 1973! Apart from the normal binary tree structures it described threaded trees, ring and multi-way trees.
2: Ring or loop Trees
These are basically binary (or any other normal kind of) tree which uses some of its sibling links to point back to a parent or grand-parent tree node. The most important thing to note about these kinds of trees is that they circular, infinite paths can be defined from which there is no escape. Also they break the parent-to-sibling rule, parent nodes DO NOT alway point to child nodes - they can point to grand-parent or grand..grand-parent etc.
These structures can be very useful to navigating back 'up' the tree towards the root OR even onto a completely different branch or tree. Of course normal trees can be extended to allow back links (sibling --> parent nodes) so that bi-directional tree climbing can be done.
3: Threaded Trees
Put simply, binary trees are empty, dead looking twig-like trees and threaded trees look like an xmas tree with xmas lights from branch to branch. The 'thread' are just links between leaves. As the leaves of a tree are normally identical to nodes except their sibling links are null (equal to 0) they are just going to waste. Usually if a node link equals zero then it is treated as a leaf of some kind. A main problem with navigating any form of tree is visiting the leaves without having to traverse every possible path through the tree. One solution is to maintain a separate list of leaves outside of the tree structure. Another could be to build a 'leaf-neighbour' link into the nodes. These would affectively be sideways links to point to the next tip of the tree's branches. In the below diagram we have just 3 nodes (A, B and C). Both nodes B and C are leaf nodes so their left and right links are null.
e.g. A
/ \
/ \
/ \
/ \
B C
/ \ / \
/ \ / \
null null null null
This can be described in a table like this:
Node left link right link
---- --------- ----------
A node B node C
B -null- -null-
C -null- -null-
A "threaded" tree uses an extra bit for every link in each node structure. This bit indicates whether the link is a true link (points to a sibling) or a "thread" (null link). Now any null links can be used to point to neighbouring leaves.
Node left link right link
---- --------- ----------
A 0 node B 0 node C
B 1 thread A 1 thread C
C 1 thread B 1 thread A
In the above table we now have one extra bit for each link. A '0' bit indicates a normal link to a sibling node. A '1' bit denotes a 'thread' (was a null link).
NOTE: I have chosen to point the leftmost and rightmost nodes back to the root node, but they could have been made to point to the opposite side of the tree - to wrap around.
e.g.
Node left link right link
---- --------- ----------
A 0 node B 0 node C
B 1 thread C 1 thread C
C 1 thread B 1 thread B
Given just one leaf we can immediately find the next or the previous leaf just by following a thread without having to traverse the tree everytime.
4: Multi-way Trees
These are just trees which have more than 2 links for each node, they can have 3, 4 or any number of links for each node. For example oct-tree use 8 links for each node and quad-trees use 4 links. Using multi-way trees does mean that far more than just 2 links can be used but there are some disadvantages. Firstly the node data structures will become increasingly bigger with each new link added. Secondly a simply true/false condition cannot be used to select more than 2 links.
5: Side Links & Lop-Sided Trees
Sometimes you find that you need a variable number of links from a node but don't want to waste tons of memory for those nodes which only require one or two. This is the situation which I found myself in when writing a LZ compression routine a number of years ago. The routine needed to find the longest matching string in an expanding dictionary, so what I did was to use a binary tree but in a lop-sided way. Instead of the normal left and right links I used 'side' and 'longer' links.
longer links --
A ---P ---E
³ ³
³
³ P ---L ---E
side links
³ R ---C ---H ---E ---R ---Y
³
S ---H ---E ---S
³
Y
The above lop-sided binary tree or 'side tree' as I call it is very useful for finding variable length strings. Believe it or not but that tree describes about 10 English words:
APE, APPLE, ARC, ARCH, ARCHER, ARCHERY, AS, ASH, ASHES, ASHY
The rules for creating and navigating this type of tree is very easy and fast. Compare the first letter with your search string's first letter. If it matches then take the 'longer' link to your right and advance to the next letter in your search string. If it does not match then take the 'side' link down until you find one that matches your search letter or a dead end.